Sudoku Solver

Description#

Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:

Row
Column
Nine 3x3 sub-boxes of the grid

Let us take a look at an example:

Problem

1 of 3

Rule

2 of 3

Solution

3 of 3

Solution#

While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, and we will have to try some other combination. To do that, we will have to use backtracking.

Let us go over the algorithm:

Start filling the board from board[0][0]
If the value is not ., move on to the next position; otherwise, fill it.
Iterate over each value from 1 to 9:
1. Check if the value is not already present in that row, column, or 3x3 sub-matrix. If no, then move on to the next value; otherwise, move to the next step.
2. Place the value on the board and move to the next position recursively.
3. If we can not place any value from 1 to 9 on a position, then change the value filled in the previous cell and retry.

Let us take a look at an example:

defmodule Solution do
  @digits ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
  def solve_sudoku(board) do
    solve(board, 0, 0) |> elem(1)
  end
  # Replace board value with digit
  def solve(board, r, c, d), do: Arrays.replace(board, r, Arrays.replace(board[r], c, d))
  # Move right until you get to end, then restart at next row
  def solve(board, r, c) when c == 9, do: solve(board, r + 1, 0)
  # Checking if we reached end of matrix
  def solve(board, r, _c) when r == 9, do: {true, board}
  def solve(board, r, c) do
    cond do
      # If no empty space exists on current col, move to next col
      Arrays.get(board[r], c) != "." -> solve(board, r, c + 1)
      true ->
        # Reduce over values
        @digits 
        |> Enum.reduce_while({false, board}, fn(d, {res, board}) ->
          cond do
            # Check if the piece can be played on the current spot
            can_play(board, r, c, d) ->
              # If yes, update the board
              board = solve(board, r, c, d)
              # And move to the next col of current row
              {res, board} = solve(board, r, c + 1)

Enter to Rename, Shift+Enter to Preview

Sudoku Solver

Description#

Coding exercise#

Solution#

Complexity measures#

Time complexity#

Space complexity#